package leetcode.code0765;

import java.util.ArrayList;
import java.util.List;

public class Solution1 extends Solution765 {

	private int[] sitIn;// sit[x] = y; x人坐在y位置
	private int[] sitOn;// sit[x] = y; x人坐在y对情侣位置
//	private int[] stack2couple;// 放置错误的情侣
//	private int[] couple2stack;// 错误的情侣在栈里的位置
//	private int pstack;

	@Override
	public int minSwapsCouples(int[] row) {
		int N2 = row.length;
		sitIn = new int[N2];
		sitOn = new int[N2];
//		stack2couple = new int[N2 >> 1];
//		pstack = -1;
//		couple2stack = new int[N2 >> 1];
		List<Integer> wrongCouple = new ArrayList<>();
		for (int i = 1, couple = 0; i < N2; i = i + 2, couple++) {
			sitIn[row[i - 1]] = i - 1;
			sitIn[row[i]] = i;
			sitOn[row[i - 1]] = couple;
			sitOn[row[i]] = couple;
			if (row[i - 1] != this.another(row[i])) {
				wrongCouple.add(couple);
//				stack2couple[++pstack] = couple;
//				couple2stack[couple] = pstack;
			}
		}
		if (wrongCouple.size() == 0)// 没有错的位置
			return 0;
		return this.f(row, wrongCouple);
	}

	private int f(int[] row, List<Integer> wrongCouple) {
		if (wrongCouple.size() == 0) {
			return 0;
		}
		int couple1 = wrongCouple.get(0);
		int sit1 = couple1 << 1;
		int sit3 = couple1 << 1 | 1;
		int a1 = row[sit1];
		int x = row[sit3];
		int a2 = this.another(a1);
		int couple2 = this.sitOn[a2];
		int sit2 = this.sitIn[a2];
		int sit4 = this.another(sit2);
		int y = row[sit4];
		if (this.another(x) == y) {
			wrongCouple.remove((Object)couple1);
			wrongCouple.remove((Object)couple2);
			return this.f(row, wrongCouple) + 1;
		}
		row[sit3] = a2;
		row[sit2] = x;
		wrongCouple.remove((Object)couple1);
		sitIn[x] = sit2;
		sitOn[x] = couple2;
		return this.f(row, wrongCouple) + 1;
	}


	private int another(int one) {// 情侣编号
		return (one & 1) == 1 ? one - 1 : one + 1;
	}


//	private int markWrongPlace(int wrong, int index) {
//		return wrong | (1 << index);
//	}
//
//	private int markRightPlace(int wrong, int index) {
//		return wrong ^ (1 << index);
//	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
